The present invention relates to a method and component for interpolating data.
In the area of image and video processing, there is frequently a need to create new images by re-sampling an original image.
Typical instances are:
a) zooming-in, where there is a need to create more pixels than in the original image;
b) Image-rotation, where new pixels overlap 2 or more of the original pixels; and
c) Image-distortion (morphing), where the aim may be to correct lens aberration (barrel, pin-cushion distortion) or even to deliberately introduce distortion.
Several two-dimensional techniques for computing new pixel-values are well known, and used frequently. The most commonly met ones are:
a) Nearest-neighbour
b) Bilinear
c) Bicubic
Nearest-neighbour is extremely simple. It consists of sampling the pixel nearest to the centre of the desired new pixel, and using that value. Unfortunately, it has the undesirable effect of introducing xe2x80x98jaggiesxe2x80x99 or xe2x80x98staircasingxe2x80x99. Consider the case of a horizontal line, 1 pixel wide. This appears to the eye as a perfect, straight line (which it is). If re-sampled using nearest-neighbour, a very-slight image-rotation of a degree or so will convert this line into a highly visible staircase. Further operations will enhance this effect, and can even cause break-up of the original line. This form of interpolation is not considered further, as the quality is very poor.
Bilinear is more complex. It consists of taking the 4 pixels which surround, the position of the new pixel, and computing a new pixel-value based on these 4 neighbours. Whichever pixel is nearest to the new one has most weight. If the new pixel is right in the middle of the 4 neighbours, then it will end up being the average of the 4 pixels. This technique is a considerable improvement on nearest neighbour, but still has some draw-backs. It has the effect of blurring the original image, and losing contrast, as the new pixel""s computed value will never lie outside the min-max range of the 4 neighbours.
Bicubic is recognised as being the xe2x80x98bestxe2x80x99 quality, as it applies a curve-fit to the pixel-values, and so is attempting to re-construct the original waveform which gave rise to the sampled pixel-values in the original image. Unfortunately, bicubic interpolation is recognised as being expensive computationally.
The present invention provides a new type of interpolation, a hybrid linear-bicubic interpolation, which achieves the quality of a bicubic interpolation, but using some 80% of the computation of traditional bicubic interpolation.
According to the invention there is provided a method of determining an interpolated value for a point lying between second and third rows of an array comprising at least four rows of spatially related points each having respective values, said method comprising the steps of: linearly interpolating between a first two points on said first row to determine a first value at a first location; cubically interpolating between a second two points on said second row in accordance with the rate of change of values at said second two points on said second row to determine a second value at a second location; cubically interpolating between a third two points on said third row in accordance with the rate of change of values at said third two points on said third row to determine a third value at a third location; linearly interpolating between a fourth two points on said fourth row to determine a fourth value at a fourth location; said first, second, third and fourth locations forming a transverse row intersecting said point; and cubically interpolating between said second and third locations in accordance with the rate of change of values at said second and third locations determined according to said first and fourth values to determine said interpolated value.